﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SmartMathLibrary
{
    /// <summary>
    /// This class provides the splitting of a natural number in two factors by using
    /// the algorithm of Fermat.
    /// </summary>
    [Serializable]
    public class FermatNumberFactorizer : AbstractNumberFactorizer
    {
        /// <summary>
        /// Initializes a new instance of the <see cref="FermatNumberFactorizer"/> class.
        /// </summary>
        /// <param name="number">The number to factorize.</param>
        public FermatNumberFactorizer(UInt64 number)
            : base(number)
        {
        }

        /// <summary>
        /// Factorizes the specified number by using the algorithm of Fermat.
        /// </summary>
        /// <returns>The factors of the number.</returns>
        public override ulong[] Factorize()
        {
            double n = this.Number;
            int x = (int) Math.Ceiling(Math.Sqrt(n));
            double r = Math.Pow(x, 2) - n;
            ulong[] result = new ulong[2];

            while (!ExtendedMath.IsSquareNumber(r))
            {
                r = r + 2 * x + 1;
                x = x + 1;
            }

            double y = Math.Sqrt(r);

            result[0] = (ulong) (x + y);
            result[1] = (ulong) (x - y);

            return result;
        }
    }
}